Theorem

There exists a TM 𝒰\mathcal{U} such that for every x,α{0,1}x, \alpha \in \{0,1\}^*, 𝒰(x,α)=Mα(x)\mathcal{U}(x,\alpha) = M_\alpha(x), where MαM_\alpha denotes the TM represented by α\alpha.
Moreover, if MαM_\alpha halts on input xx within TT steps then 𝒰(x,α)\mathcal{U}(x,\alpha) halts within CTlogTCT\log T steps, where CC is a number independent of |x|\lvert x \rvert and depending only on MαM_\alpha's alphabet size, and number of states.


References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 20.
  2. https://www.cs.princeton.edu/courses/archive/spr06/cos522/lec2.pdf